---
title: "发现环"
created: 2025-11-28
tags:
  - 算法
---

# 发现环

## 题目 [发现环](https://www.lanqiao.cn/paper/3857/problem/108/)

![[image-838680ef.png]]

## 思路分析

发现忘了怎么存图 直觉告诉是用并查集 但是也是忘了咋用emmm 好 该复习的点找到了

因为这条路卡住了 就想着换一个方式解决 用快慢指针的方式 遍历图构造链表 再在链表中使用快慢指针判断是否有环  但由于链表是单后继
图是多后继 要这样做就只能把每种情况都拆分开来构造一个链表再做 显然耗时耗力

再或者直接用bfs遍历树  记录每个节点的父节点是谁 当访问到一个已经访问过的节点时 就是发现环 接着回溯父节点找到环的组成

回头再看吧 这题留着复习后自检用

## 代码实现

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
const int MAX_EDGES = 200010;

int head[MAX_N], to[MAX_EDGES], nxt[MAX_EDGES], ecnt;
int parent[MAX_N], visited[MAX_N];
vector<int> cycle;

void add_edge(int u, int v) {
    to[ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt++;
}

void find_cycle(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    parent[start] = -1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (!visited[v]) {
                visited[v] = 1;
                parent[v] = u;
                q.push(v);
            } else if (parent[u] != v) {
                // 发现环
                set<int> unique_nodes;
                int cur = u;
                while (cur != -1 && unique_nodes.find(cur) == unique_nodes.end()) {
                    unique_nodes.insert(cur);
                    cur = parent[cur];
                }
                cur = v;
                while (cur != -1 && unique_nodes.find(cur) == unique_nodes.end()) {
                    unique_nodes.insert(cur);
                    cur = parent[cur];
                }
                cycle.assign(unique_nodes.begin(), unique_nodes.end());
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    fill(head, head + MAX_N, -1);
    ecnt = 0;

    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    memset(visited, 0, sizeof visited);
    find_cycle(1);

    sort(cycle.begin(), cycle.end());

    for (int node : cycle) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[希尔伯特曲线|希尔伯特曲线]] 🏠 [[00-冲刺国赛]] ➡️ [[对局匹配|对局匹配]]